package org.totoro.structure.tree;

import org.totoro.structure.list.List;
import org.totoro.structure.list.impl.ArrayList;
import org.totoro.structure.queue.Queue;
import org.totoro.structure.queue.impl.ArrayQueue;
import org.totoro.structure.stack.Stack;
import org.totoro.structure.stack.impl.ArrayStack;

import java.util.Objects;

/**
 * 二分叉 搜索树
 * <p>
 * 特性：left 的值 必须小于 rigth 的值
 *
 * @author daocr
 * @date 2020/3/24
 * <p>
 * 深度遍历遍历
 * @see BinarySearchTree#depthTraversal()
 * 广度遍历
 * @see BinarySearchTree#breadthTraversal()
 * 中序遍历，可自然排序
 * @see BinarySearchTree#middleTraversal(List, TreeNode)
 * 最大值
 * @see BinarySearchTree#getMax(TreeNode)
 * 最小值
 * @see BinarySearchTree#min(TreeNode)
 */
public class BinarySearchTree<E extends Comparable<E>> implements Tree<E> {

    private int size;

    private TreeNode<E> root;

    public int getSize() {
        return size;
    }

    public TreeNode<E> getRoot() {
        return root;
    }

    public BinarySearchTree() {

    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean contains(E element) {
        return Objects.nonNull(find(element));
    }

    @Override
    public boolean add(E element) {

        if (root == null) {
            root = new TreeNode<>(element);
            size++;
            return true;
        }

        add(root, element);

        size++;

        return true;

    }

    private TreeNode<E> add(TreeNode<E> node, E element) {

        /**
         * 如果小于等于当前节点就一直往左边找
         */
        if (element.compareTo(node.element) <= 0) {
            if (node.left == null) {
                node.left = new TreeNode<>(element);
                return node;
            }
            add(node.left, element);
        }
        /**
         * 如果大于等于当前节点就一直往右边找
         */
        if (element.compareTo(node.element) > 0) {
            if (node.right == null) {
                node.right = new TreeNode<>(element);
                return node;
            }
            add(node.right, element);
        }

        return node;

    }

    public boolean remove(E element) {
        return remove(root, element) != null;
    }

    /**
     * <p>
     * <p>
     * 1962年，Hibbard提出Hibbard Deletion
     *
     * @param node
     * @param element
     * @return
     */

    private TreeNode<E> remove(TreeNode<E> node, E element) {

        if (node == null) {
            return null;
        }

        // 向左遍历
        if (element.compareTo(node.element) < 0) {
            TreeNode<E> remove = remove(node.left, element);
            node.left = remove;
            return node;
        }
        if (element.compareTo(node.element) > 0) {
            TreeNode<E> remove = remove(node.right, element);
            node.right = remove;
            return node;
        }

        if (element.compareTo(node.element) == 0) {
            // 待删除的左节点为 null
            if (node.left == null) {
                return node.right;
            }

            // 待删除的右边节点为 null
            if (node.right == null) {
                return node.left;
            }

            // 获取最小的节点
            TreeNode<E> maxNode = min(node.right);
            TreeNode<E> removeMin = removeMin(node.right);
            maxNode.right = removeMin;
            maxNode.left = node.left;
            node.left = node.right = null;

            return maxNode;
        }

        return node;

    }

    public void removeMax() {
        root = removeMax(root);
    }

    public void removeMin() {
        root = removeMin(root);
    }

    /**
     * 删除最大值
     * 1、返回 right 节点，没有孩子节点返回null；
     * 2、把返回值赋给 left 节点
     *
     * @param node
     * @return
     */
    public TreeNode<E> removeMax(TreeNode<E> node) {
        /*
         * 找到最小值
         */
        if (node.right == null) {
            size--;
            return node.left;
        }

        //  通过找到的右边节点  把右边的子树，迁移到左边，可以不破坏整颗树结构
        node.right = removeMax(node.right);

        return node;
    }


    /**
     * 删除最小值
     * <p>
     * 1、返回left 节点，没有孩子节点返回null；
     * 2、把返回值赋给 left 节点
     *
     * @param node
     * @return
     */
    public TreeNode<E> removeMin(TreeNode<E> node) {

        /*
         * 找到最小值
         */
        if (node.left == null) {
            size--;
            return node.right;
        }

        //  通过找到的右边节点  把右边的子树，迁移到左边，可以不破坏整颗树结构
        node.left = removeMin(node.left);

        return node;
    }

    /**
     * 循环遍历
     *
     * @param element
     * @return
     */
    private TreeNode<E> find(E element) {

        if (root == null) {
            return null;
        }

        TreeNode<E> curNode = root;

        while (curNode != null) {

            if (curNode.element.compareTo(element) == 0) {
                return curNode;
            }

            if (curNode.element.compareTo(element) > 0) {
                curNode = curNode.left;
            }

            if (curNode.element.compareTo(element) < 0) {
                curNode = curNode.right;
            }
        }

        return null;
    }

    /**
     * 获取最小值
     *
     * @param node
     * @return
     */
    private TreeNode<E> min(TreeNode<E> node) {

        if (node.left == null) {
            return node;
        }

        return min(node.left);
    }

    /**
     * 计算高度
     *
     * @param node
     * @return
     */
    public int calculateHeight(TreeNode<E> node) {

        if (node == null) {
            return 0;
        }

        node.height = Math.max(calculateHeight(node.left), calculateHeight(node.right)) + 1;

        return node.height;
    }


    /**
     * 计算最大深度
     *
     * @param root
     * @return
     */
    public int calculateMaxDepth(TreeNode<E> root) {
        return calculateMaxDepth(root, 0);
    }

    private int calculateMaxDepth(TreeNode<E> root, int depth) {

        if (root == null) {
            return depth -1;
        }

        int left = calculateMaxDepth(root.left, depth + 1);
        int right = calculateMaxDepth(root.right, depth + 1);

        return Math.max(left, right) ;
    }


    /**
     * 获取最大值
     *
     * @param node
     * @return
     */
    private TreeNode<E> getMax(TreeNode<E> node) {

        if (node.right == null) {
            return node;
        }
        return min(node.right);
    }

    public E get(int index) {
        return null;
    }

    public E getLast() {
        return null;
    }


    /**
     * 中序遍历 , 可以实现排序
     *
     * @return
     */
    public List<E> srot() {
        return middleTraversal(new ArrayList<E>(), root);
    }

    public List<E> middleTraversal(List<E> list, TreeNode<E> node) {

        if (node == null) {
            return null;
        }

        middleTraversal(list, node.left);
        list.add(node.element);
        middleTraversal(list, node.right);

        return list;
    }

    /**
     * 深度 遍历
     * <p>
     * 利用栈先进后出的特性，记录程序位置
     *
     * @return
     */
    public List<E> depthTraversal() {

        List<E> result = new ArrayList<>();
        TreeNode<E> root = this.root;

        Stack<TreeNode<E>> stack = new ArrayStack<>();
        stack.push(root);

        while (!stack.isEmpty()) {

            TreeNode<E> pop = stack.pop();
            if (pop.right != null) {
                stack.push(pop.right);
            }

            if (pop.left != null) {
                stack.push(pop.left);
            }
            result.add(pop.element);
        }

        return result;

    }

    /**
     * 广度 遍历
     *
     * @return
     */
    public List<E> breadthTraversal() {

        List<E> result = new ArrayList<>();

        TreeNode<E> root = this.root;

        Queue<TreeNode<E>> queue = new ArrayQueue<>();

        queue.enqueue(root);
        while (!queue.isEmpty()) {

            TreeNode<E> dequeue = queue.dequeue();
            result.add(dequeue.element);

            if (dequeue.left != null) {
                queue.enqueue(dequeue.left);
            }

            if (dequeue.right != null) {
                queue.enqueue(dequeue.right);
            }
        }

        return result;
    }


    public static class TreeNode<E extends Comparable<E>> {
        private TreeNode<E> left, right;
        private E element;

        private int height;

        public TreeNode(E element) {
            this.element = element;
        }

        public TreeNode<E> getLeft() {
            return left;
        }

        public TreeNode<E> getRight() {
            return right;
        }

        public E getElement() {
            return element;
        }
    }

    /**
     * @param args
     */

    public static void main(String[] args) {
        BinarySearchTree<Integer> treeNode = new BinarySearchTree<>();

        treeNode.add(41);
        treeNode.add(22);
        treeNode.add(60);
        treeNode.add(15);
        treeNode.add(33);
        treeNode.add(59);
        treeNode.add(63);
        treeNode.add(13);
        treeNode.add(37);

        treeNode.remove(22);

        System.out.println(treeNode);


    }

}
